package 中等.搜索.回溯;

import java.util.Arrays;

/**
 * 你打算做甜点，现在需要购买配料。目前共有 n 种冰激凌基料和 m
 * 种配料可供选购。而制作甜点需要遵循以下几条规则：
 * 必须选择 一种 冰激凌基料。
 * 可以添加 一种或多种 配料，也可以不添加任何配料。
 * 每种类型的配料 最多两份 。
 * 给你以下三个输入：
 * baseCosts ，一个长度为 n 的整数数组，其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。
 * toppingCosts，一个长度为 m 的整数数组，其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。
 * target ，一个整数，表示你制作甜点的目标价格。
 * 你希望自己做的甜点总成本尽可能接近目标价格 target 。
 * 返回最接近 target 的甜点成本。如果有多种方案，返回 成本相对较低 的一种。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/closest-dessert-cost
 */
public class 最接近目标价格的甜点成本_1774 {

    public static void main(String[] args) {

        System.out.println(new 最接近目标价格的甜点成本_1774().closestCost2(
                new int[]{3, 10}, new int[]{2, 5}, 9));

    }

    private int minDiffCost;

    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        minDiffCost = baseCosts[0];
        Arrays.sort(toppingCosts);

        int[] record = new int[toppingCosts.length];

        for (int baseCost : baseCosts) {
            dfs(toppingCosts, record, baseCost, target);
            if (minDiffCost == target) {
                return target;
            }
        }

        return minDiffCost;
    }

    // 每一次只花费一份配料
    private void dfs(int[] toppingCosts, int[] record, int curCost, int target) {
        if (curCost == target) {
            minDiffCost = target;
            return;
        }
        if (curCost > target) {
            if (curCost - target < Math.abs(target - minDiffCost)) {
                minDiffCost = curCost;
            }
            return;
        }
        if (target - curCost <= Math.abs(target - minDiffCost)) {
            minDiffCost = curCost;
        }

        for (int i = 0; i < toppingCosts.length; i++) {
            if (record[i] < 2) {
                record[i]++;
                dfs(toppingCosts, record, curCost + toppingCosts[i], target);
                record[i]--;
            }
        }
    }

    public int closestCost2(int[] baseCosts, int[] toppingCosts, int target) {
        minDiffCost = baseCosts[0];
        for (int baseCost : baseCosts) {
            dfs2(toppingCosts, 0, baseCost, target);
            if (minDiffCost == target) {
                return target;
            }
        }
        return minDiffCost;
    }

    // 每一种配料买的方式只有三种，不买，买一份，买两份
    private void dfs2(int[] toppingCosts, int idx, int curCost, int target) {
        if (curCost == target) {
            minDiffCost = target;
            return;
        }
        if (curCost > target) {
            if (curCost - target < Math.abs(target - minDiffCost)) {
                minDiffCost = curCost;
            }
            return;
        }
        if (target - curCost <= Math.abs(target - minDiffCost)) {
            minDiffCost = curCost;
        }
        if (idx == toppingCosts.length) {
            return;
        }
        dfs2(toppingCosts, idx + 1, curCost, target);
        dfs2(toppingCosts, idx + 1, curCost + toppingCosts[idx], target);
        dfs2(toppingCosts, idx + 1, curCost + toppingCosts[idx] * 2, target);
    }

}
